
using System;
using System.Diagnostics;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace Ack
{
	public class NesEncoder2
	{
		private static int EncodeRowDifferences(byte[] patternInput, int patternIndex, byte[] referenceInput, int referenceIndex, bool flipx, bool flipy, byte[] output, int lowestCost)
		{
			int len = 0;
			output[len++] = 0; // header 1 (reserved for RD scheme)
			output[len++] = 0; // header 2 (set bit = row is explicitly stored)
			
			for(int y = 0; y < 8; ++y)
			{
				if(len >= lowestCost) return 1000;
				
				int refy = (flipy?7-y:y);
	
				byte refByte = (byte)(referenceInput[referenceIndex*8+refy]);
				if(flipx) refByte = Misc.ReverseByte(refByte);
				
				if(patternInput[patternIndex*8+y] != refByte)
				{
					output[len++] = patternInput[patternIndex*8+y];
					output[1] |= (byte)(1 << (7-y));
				}
			}
			
			if(flipx) output[0] |= 0x80;
	
			return len;
		}
		
		private static byte[] EncodeRD(byte[] input, int patternIndex, out bool flipy)
		{
			int lowestCost = Int32.MaxValue;
			int bestIndex = -1;
			byte[] testRD = new byte[10];
			byte[] bestRD = new byte[10];
			int bestRDLength = 0;
			
			flipy = false;

			for(int i = 1; i <= 127; ++i)
			{
				int referenceIndex = patternIndex-i;
				
				if(referenceIndex < 0)
					break;
	
				for(int f = 0; f < 4; ++f)
				{
					int len = EncodeRowDifferences(input,patternIndex, input,referenceIndex,(f&1)!=0,(f&2)!=0, testRD,lowestCost);
					
					if(len < lowestCost)
					{
						lowestCost = len;
						testRD.CopyTo(bestRD,0);
						bestRDLength = len; 
						bestIndex = i;
						flipy = (f&2)!=0;
					}
				}
				
			}
			
			if(bestRDLength>0)
			{
			/*	if(bestRDLength==2)
				{
					bestRDLength=1;
		
				}
				else
			*/		bestRD[0] |= (byte)bestIndex;
				
				return Misc.TrimArray(bestRD,bestRDLength);
			}
			
			return null;
		}
		
		

		private static void GetTwoMostCommonPatterns(byte[] input, out ulong patternA, out ulong patternB)
		{
			int patternCount = input.Length / 8;
			Debug.Assert((input.Length & 7) == 0);
			
			Dictionary<ulong, int> freqs = new Dictionary<ulong, int>();
			for(int pi = 0; pi < patternCount; ++pi)
			{
				byte[] temp = Misc.TrimArray(input,pi*8,8);
				ulong key = BitConverter.ToUInt64(temp,0);
				if(!freqs.ContainsKey(key))
					freqs.Add(key,1);
				else
					freqs[key]++;
			}

			var topTwo = (from entry in freqs orderby entry.Value descending select entry.Key).Take(2).ToArray();

			patternA = topTwo[0];
			patternB = topTwo[1];
		}
		
		enum PatternMode
		{
			Raw					= 0, // pattern is stored raw (8 bytes)
			RCR					= 1, // pattern uses row/column-repeat encoding (1+n bytes)
			CommonA				= 2, // the two most common patterns in an 8KB block are found and signaled via this mode
			CommonB				= 3, // the two most common patterns in an 8KB block are found and signaled via this mode

			// Illegal for first pattern:
			SameAsLast			= 4, // pattern is equal to the preceding one (note: can span 2bit tiles)
			SameAsLastInverted	= 5, // this is fairly common between bitplanes of the same tile
			
			RD					= 6, 
			RD2    				= 7  // pattern is based on reference pattern + differing rows (2+n bytes)
		};

		public class Statistics
		{
			public int _totalPatternCount;
			public int[] _patternModeCounts = new int[] {0,0,0,0,0,0,0,0};
			public int[] _mode67Counts = new int[] {0,0,0,0};

			public override string ToString()
			{
				string s = "";
				s += "\n2 ) CommonA: " + String.Format("{0:0.00%}",(float)_patternModeCounts[(int)PatternMode.CommonA]/_totalPatternCount);
				s += "\n3 ) CommonB: " + String.Format("{0:0.00%}",(float)_patternModeCounts[(int)PatternMode.CommonB]/_totalPatternCount);
				s += "\n4 ) SameAsLast: " + String.Format("{0:0.00%}",(float)_patternModeCounts[(int)PatternMode.SameAsLast]/_totalPatternCount);
				s += "\n5 ) SameAsLastInverted: " + String.Format("{0:0.00%}",(float)_patternModeCounts[(int)PatternMode.SameAsLastInverted]/_totalPatternCount);
				
				s += "\n6a) RD: " + String.Format("{0:0.00%}",(float)_mode67Counts[0]/_totalPatternCount);
				s += "\n6b) RD(-x): " + String.Format("{0:0.00%}",(float)_mode67Counts[1]/_totalPatternCount);
				s += "\n7a) RD(-y): " + String.Format("{0:0.00%}",(float)_mode67Counts[2]/_totalPatternCount);
				s += "\n7b) RD(-x,-y): " + String.Format("{0:0.00%}",(float)_mode67Counts[3]/_totalPatternCount);
				
				s += "\n1 ) RCR: " + String.Format("{0:0.00%}",(float)_patternModeCounts[(int)PatternMode.RCR]/_totalPatternCount);
				s += "\n0 ) Raw: " + String.Format("{0:0.00%}",(float)_patternModeCounts[(int)PatternMode.Raw]/_totalPatternCount);
				return s;
			}
		};
		
		public static List<byte> Encode(byte[] input, Statistics stats)
		{
			List<byte> output = new List<byte>();
			int patternCount = input.Length / 8;
			Debug.Assert((input.Length & 7) == 0);
			
			ulong patternA, patternB;
			GetTwoMostCommonPatterns(input, out patternA, out patternB);

			output.AddRange(Misc.EncodeRowRepeats(BitConverter.GetBytes(patternA),0));
			output.AddRange(Misc.EncodeRowRepeats(BitConverter.GetBytes(patternB),0));
			
			stats._totalPatternCount += patternCount;
			
			int groupHeaderStart = 0;
			for(int pi = 0; pi < patternCount; ++pi)
			{
				byte[] patternBytes = Misc.TrimArray(input,pi*8,8);
				ulong pattern = BitConverter.ToUInt64(patternBytes.ToArray(),0);

				int indexInGroup = pi & 7;
				
				// Start of 8 pattern group?
				if(indexInGroup == 0)
				{
					// Add empty group header
					groupHeaderStart = output.Count;
					output.Add(0);
					output.Add(0);
					output.Add(0);
				}
				
                Action<PatternMode> writePatternMode = delegate(PatternMode bits)
                {
                        byte mask = (byte)(1 << (7-indexInGroup));
                        output[groupHeaderStart+0] &= (byte)~mask;
                        output[groupHeaderStart+1] &= (byte)~mask;
                        output[groupHeaderStart+2] &= (byte)~mask;
                        output[groupHeaderStart+0] |= (byte)((((int)bits & 4) != 0) ? mask : (byte)0);
                        output[groupHeaderStart+1] |= (byte)((((int)bits & 2) != 0) ? mask : (byte)0);
                        output[groupHeaderStart+2] |= (byte)((((int)bits & 1) != 0) ? mask : (byte)0);
                };
				
				// PatternMode.Common
				if(pattern == patternA)
				{
					writePatternMode(PatternMode.CommonA);
					stats._patternModeCounts[(int)PatternMode.CommonA]++;
					continue;
				}

				if(pattern == patternB)
				{
					writePatternMode(PatternMode.CommonB);
					stats._patternModeCounts[(int)PatternMode.CommonB]++;
					continue;
				}
				
				// PatternMode.SameAsLast
				// PatternMode.SameAsLastInverted
				if(pi > 0)
				{
					ulong patternPrev = BitConverter.ToUInt64(Misc.TrimArray(input,pi*8-8,8),0);

					if(pattern == patternPrev)
					{
						writePatternMode(PatternMode.SameAsLast);
						stats._patternModeCounts[(int)PatternMode.SameAsLast]++;
						continue;
					}
					
					if(pattern == ~patternPrev)
					{
						writePatternMode(PatternMode.SameAsLastInverted);
						stats._patternModeCounts[(int)PatternMode.SameAsLastInverted]++;
						continue;
					}					
				}

				// 1) Row-Repeat encoded tile
				//
				// Remove repeated rows. Store which ones are explicit as 1's in a 1 byte tile header.
				//
				// RCR Header: T1234567
				// 		T: Tile is transposed				
				// 		1-7: Row numbers that are explicit (note: row 0 is always stored)		
				byte[] rcr = Misc.EncodeRCR(patternBytes,0);
			
				
				// 6-7) Row Difference encoding, find "best" earlier pattern and store differing rows.
				// 
				// RD header: xppppppp  (x=unused, p=pattern offset)
				//            01234567  0-7: Rows that are stored (n=# bits set)
				// Then follow "n" stored rows.
				bool rdflipy;
				byte[] rd = EncodeRD(input, pi, out rdflipy);
				if(rd != null && rd.Length > 0 && rd.Length < rcr.Length && rd.Length < 8)
				{
					if(rdflipy)
					{
					//	stats._patternModeCounts[(int)PatternMode.RD2]++;
						
						if((rd[0] & 0x80)!=0)
							stats._mode67Counts[3]++;
						else
							stats._mode67Counts[2]++;
							
						stats._patternModeCounts[(int)PatternMode.RD2]++;
						writePatternMode(PatternMode.RD2);
					}
					else
					{
						if((rd[0] & 0x80)!=0)
							stats._mode67Counts[1]++;
						else
							stats._mode67Counts[0]++;
						
						stats._patternModeCounts[(int)PatternMode.RD]++;
						writePatternMode(PatternMode.RD);
					}

					output.AddRange(rd);
					continue;
				}
				else if(rcr.Length < 8) // 8 is the cost of a raw pattern
				{
					writePatternMode(PatternMode.RCR);
					stats._patternModeCounts[(int)PatternMode.RCR]++;
					output.AddRange(rcr);
					continue;
				}
				
				// 0) Fallback: raw encoded tile
				writePatternMode(PatternMode.Raw);
				stats._patternModeCounts[(int)PatternMode.Raw]++;
				output.AddRange(patternBytes);
			}
						
			return output;
		}
	
		
	}
}
